package xyz.scootaloo.oj.leetcode

import org.junit.Test
import xyz.scootaloo.common.TestDsl

/**
 * @author flutterdash@qq.com
 * @since 2021/7/9 21:45
 */
class P118 : TestDsl {

    private fun generate(numRows: Int): List<List<Int>> {
        val res = ArrayList<ArrayList<Int>>().apply {
            for (i in 0 until numRows) {
                add(ArrayList<Int>(i + 1).apply {
                    for (j in 0..i)
                        add(0)
                })
            }
        }

        // init
        res[0][0] = 1
        for (r in 1 until numRows) {
            res[r][0] = 1
            res[r][r] = 1
        }

        for (r in 2 until numRows) {
            for (c in 1 until r) {
                res[r][c] = res[r - 1][c - 1] + res[r - 1][c]
            }
        }

        return res
    }

    @Test
    fun test0() {
      generate(13).log()
      generate(5).log()
    }

}
